#!/usr/bin/python
# -*- coding: utf8 -*-

import sys
import os



from common import *
from rule import *


class GrammarNode:
    def __init__(self, symbol, position):
        self.symbol = symbol
        if len(position) == 2:
            self.position = position
        else:
            self.position = position * 2
        self.derives = []

    def append_derive(self, rule, nodes):
        self.derives.append(GrammarDerive(rule, nodes))

    def left(self):
        return self.position[0]

    def right(self):
        return self.position[1]

    def identity_string(self):
        return '%s(%d, %d)' % (self.symbol, self.position[0], self.position[1])

    def debug_string(self, ident, words):
        space = u' ' * ident
        lines = [space + '%s(%s)' % (self.symbol, sub_words(words, self.position))]
        for d in self.derives:
            lines.append(d.debug_string(ident + 1, words))
        return u'\n'.join(lines)


class GrammarDerive:
    def __init__(self, rule, nodes):
        self.rule = rule
        self.nodes = nodes

    def debug_string(self, ident, words):
        space = u' ' * ident
        lines = [space + '#' +  self.rule.debug_string()]
        for n in self.nodes:
            lines.append(n.debug_string(ident + 1, words));
        return u'\n'.join(lines)


class GrammarTree:
    def __init__(self, root):
        self.root = root

    def debug_string(self, words):
        return self.root.debug_string(0, words)

# parse grammar tree using CKY
class CKYPath:
    def __init__(self, rule, path):
        self.rule = rule
        self.path = path

        check_type(path, tuple)
        if len(rule.rhs) != len(path):
            raise


    def debug_string(self, words):
        path = self.path
        if len(path) == 2:
            return u"%s,%s(%s)" % (sub_words(words, path[0]),
                                   sub_words(words, path[1]),
                                   self.rule.debug_string())
        else:
            return u"%s(%s)" % (sub_words(words, path[0]), self.rule.debug_string())


class CKYNode:
    def __init__(self):
        self.symbols = {}
    
    def append_path(self, rule, *path):
        s = rule.lhs
        if s not in self.symbols:
            self.symbols[s] = []
        self.symbols[s].append(CKYPath(rule, path))

    def debug_string(self, words):
        lines = [p.debug_string(words) for s in self.symbols.values() for p in s]
        return u'\n'.join(l for l in lines if l != "")


class CKYParser:
    def __init__(self):
        self.cky = None


    def build_node(self, l, r):
        for i in range(l, r):
            path = ((l, i), (i + 1, r))
            for A in self.cky[l][i].symbols:
                for B in self.cky[i+1][r].symbols:
                    rules = get_rules_by_rhs((A, B))
                    if rules == None:
                        continue
                    for rule in get_rules_by_rhs((A, B)):
                        self.cky[l][r].append_path(rule, (l, i), (i + 1, r))


    def parse(self, types):
        length = len(types)
        self.cky = [[CKYNode() for j in range (0, length)] for i in range(0, length)]
        for i in range(0, length):
            for s in types[i]:
                for r in get_rules_by_rhs(tuple([s])):
                    self.cky[i][i].append_path(r, (i, i))
        for i in range(1, length):
            for j in range(0, length - i):
                self.build_node(j, j + i)


    def build_grammar_tree(self):
        length = len(self.cky)
        root = GrammarNode('START', (0, length - 1)) 
        nodes = {}
        nodes[(root.symbol, root.position)] = root
        
        process_list = [root]
        for node in process_list:
            if is_terminal(node.symbol):
                continue
            cky_node = self.cky[node.left()][node.right()]
            for cky_path in cky_node.symbols[node.symbol]:
                num = len(cky_path.path)
                ids = [(cky_path.rule.rhs[i], cky_path.path[i]) \
                        for i in range(0, num)]
                derives = []
                for i in ids:
                    if i in nodes:
                        derive_node = nodes[i]
                    else:
                        derive_node = GrammarNode(i[0], i[1])
                        process_list.append(derive_node)
                    derives.append(derive_node)
                node.append_derive(cky_path.rule, derives)

        return GrammarTree(root)


    def debug_string(self, words):
        length = len(self.cky)
        lines = [self.cky[i][j].debug_string(words)
                for i in range(0, length) for j in range(0, length)] 
        return u'\n'.join(l for l in lines if l != "")
